#include <stdio.h>
#include "common.h"

/*
    二分查找算法实现
    经典题目：假设我们有 1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB，如何实现？
    二分查找是一种非常高效的查找算法，具有O(logn) 惊人的查找速度。
*/

int bsearch(int array[], int n, int value);
int bsearch2(int array[], int n, int value);
int bsearch3(int array[], int n, int value);
int bsearch4(int array[], int n, int value);
int bsearch5(int array[], int n, int value);

void main()
{
    int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 10, 18};

    printf("%d\n", bsearch3(array, sizeof(array) / sizeof(int), 18));
}

int bsearch(int array[], int n, int value)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        // 中间元素的下标
        int middle = low + ((high - low) >> 1);
        if (array[middle] == value)
        {
            return middle;
        }
        else if (array[middle] < value)
        {
            low = middle + 1;
        }
        else
        {
            high = middle - 1;
        }
    }
    return -1;
}

/* 变体一：查找第一个值等于给定值的元素 */
int bsearch2(int array[], int n, int value)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = low + ((high - low) >> 1);
        if (array[mid] > value)
        {
            high = mid - 1;
        }
        else if (array[mid] < value)
        {
            low = mid + 1;
        }
        else
        {
            if (mid == 0 || array[mid - 1] != value)
                return mid;
            high = mid - 1;
        }
    }
    return -1;
}

/* 变体二：查找最后一个值等于给定值的元素 */
int bsearch3(int array[], int n, int value)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = low + ((high - low) >> 1);
        if (array[mid] > value)
        {
            high = mid - 1;
        }
        else if (array[mid] < value)
        {
            low = mid + 1;
        }
        else
        {
            if (mid == n - 1 || array[mid + 1] != value)
                return mid;
            low = mid + 1;
        }
    }
    return -1;
}

/* 变体三：查找第一个值大于或等于给定值的元素 */
int bsearch4(int array[], int n, int value)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = low + ((high - low) >> 1);
        if (array[mid] >= value)
        {
            if (mid == 0 || array[mid - 1] < value)
            {
                return mid;
            }
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }

    return -1;
}

/* 变体四：查找最后一个值小于或等于给定值的元素 */
int bsearch5(int array[], int n, int value)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = low + ((high - low) >> 1);
        if (array[mid] > value)
        {
            high = mid - 1;
        }
        else
        {
            if (mid == n - 1 || array[mid + 1] > value)
            {
                return mid;
            }
            low = mid + 1;
        }
    }

    return -1;
}